package cn.myworld.algorithm.symbol;

/**
 * 符号表
 * @param <Key>
 * @param <Value>
 */
public class SymbolTable<Key, Value> {

    private Node head;
    private int N;

    private class Node {
        public Key key;
        public Value value;
        public Node next;
        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable() {
        this.head = new Node(null, null, null);
        this.N = 0;
    }

    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return N == 0;
    }

    // 插入键值对
    public void put(Key key, Value value) {
        // 如果符号表中已经存在了键为key的键值对，那么找到改节点，覆盖其value
        Node n = head;
        while (n.next != null) {
            // 变换n
            n = n.next;
            // 判断节点储存的键是否为key，如果是，则替换
            if (n.key.equals(key)) {
                n.value = value;
                return;
            }
        }
        // 如果不存在，那么创建新节点，保存要查出的键值对，插入到链表的头部（头插法）
        Node newNode = new Node(key, value, null);
        Node oldFirst = head.next;
        newNode.next = oldFirst;
        head.next = newNode;

        // 元素个数+1
        N++;

    }
    // 删除key的键值对
    public void delete(Key key) {
        // 找到键为key的节点，把该节点从链表中删除
        Node n = head;
        while (n.next != null) {
            // 判断n节点的下一个节点的键是否为key，如果是，就删除节点
            if (n.next.key.equals(key)) {
                n.next = n.next.next;
                N--;
                return;
            }

            // 变换n
            n = n.next;
        }
    }
    // 获取key的value
    public Value get(Key key) {
        Node n = head;
        // 找到键为key的节点
        while (n.next != null) {
            // 变换n
            n = n.next;
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }

}
